package leetcode;


/**
 * Created by Ghost on 2014/10/11 0011.
 */
public class Balanced_Binary_Tree {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int left = getHight(root.left);
        int right = getHight(root.right);
        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int getHight(TreeNode root){
        if(root==null)
            return 0;
        int left = 1+getHight(root.left);
        int right = 1+getHight(root.right);
        return left>right?left:right;
    }
    public static void main(String[] args){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
//      root.left.left.left = new TreeNode(6);
        root.right.right.right = new TreeNode(7);
        Balanced_Binary_Tree balanced_binary_tree = new Balanced_Binary_Tree();
        System.out.println(balanced_binary_tree.isBalanced(null));
    }
}
